class MedianFinder {
public:
    priority_queue<int, vector<int>, less<int>> less;
    priority_queue<int, vector<int>, greater<int>> greater;

    MedianFinder()
    {

    }

    void addNum(int num) {

        if (less.empty() == true || num < less.top())
        {
            less.push(num);
            if (less.size() > greater.size() + 1)
            {
                greater.push(less.top());
                less.pop();
            }
        }
        else
        {
            greater.push(num);
            if (greater.size() > less.size())
            {
                less.push(greater.top());
                greater.pop();
            }

        }


    }

    double findMedian()
    {
        if (less.size() > greater.size()) return less.top();
        else return (less.top() + greater.top()) / 2.0;
    }
};

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder* obj = new MedianFinder();
 * obj->addNum(num);
 * double param_2 = obj->findMedian();
 */